Networks and distributed storage allow data and storage space to be shared between devices located anywhere a connection is available. These implementations may range from a single machine offering a shared drive over a home network to an enterprise-class cloud storage array with multiple copies of data distributed throughout the world. Larger implementations may incorporate Network Attached Storage (NAS) devices, Storage Area Network (SAN) devices, and other configurations of storage elements and controllers in order to provide data and manage its flow. Improvements in distributed storage have given rise to a cycle where applications demand increasing amounts of data delivered with reduced latency, greater reliability, and greater throughput. Hand-in-hand with this trend, system administrators have taken advantage of falling storage prices to add capacity wherever possible.
To provide this capacity, increasing numbers of storage elements have been added to increasingly complex storage systems. To accommodate this, the storage systems utilize one or more layers of indirection that allow connected systems to access data without concern for how it is distributed among the storage devices. The connected systems issue transactions directed to a virtual address space that appears to be a single, contiguous device regardless of how many storage devices are incorporated into the virtual address space. It is left to the storage system to translate the virtual addresses into physical addresses and provide them to the storage devices. RAID (Redundant Array of Independent/Inexpensive Disks) is one example of a technique for grouping storage devices into a virtual address space, although there are many others. In these applications and others, indirection hides the underlying complexity from the connected systems and their applications.
RAID and other indirection techniques maintain one or more tables that map or correlate virtual addresses to physical addresses or other virtual addresses. However, as the sizes of the address spaces grow, the tasks of managing and searching the tables may become a bottleneck. The overhead associated with these tasks is non-trivial, and many implementations require considerable processing resources to manage the mapping and require considerable memory to store it. Accordingly, an improved system and technique for performing lookups such as those used in mapping addresses would be desirable to dramatically improve storage system performance.